// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_NODE_CACHE_H_
#define V8_COMPILER_NODE_CACHE_H_

#include "src/base/export-template.h"
#include "src/base/functional.h"
#include "src/base/macros.h"

namespace v8 {
namespace internal {

    // Forward declarations.
    class Zone;
    template <typename>
    class ZoneVector;

    namespace compiler {

        // Forward declarations.
        class Node;

        // A cache for nodes based on a key. Useful for implementing canonicalization of
        // nodes such as constants, parameters, etc.
        template <typename Key, typename Hash = base::hash<Key>,
            typename Pred = std::equal_to<Key>>
        class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) NodeCache final {
        public:
            explicit NodeCache(unsigned max = 256)
                : entries_(nullptr)
                , size_(0)
                , max_(max)
            {
            }
            ~NodeCache() = default;

            // Search for node associated with {key} and return a pointer to a memory
            // location in this cache that stores an entry for the key. If the location
            // returned by this method contains a non-nullptr node, the caller can use
            // that
            // node. Otherwise it is the responsibility of the caller to fill the entry
            // with a new node.
            // Note that a previous cache entry may be overwritten if the cache becomes
            // too full or encounters too many hash collisions.
            Node** Find(Zone* zone, Key key);

            // Appends all nodes from this cache to {nodes}.
            void GetCachedNodes(ZoneVector<Node*>* nodes);

        private:
            struct Entry;

            Entry* entries_; // lazily-allocated hash entries.
            size_t size_;
            size_t max_;
            Hash hash_;
            Pred pred_;

            bool Resize(Zone* zone);

            DISALLOW_COPY_AND_ASSIGN(NodeCache);
        };

        // Various default cache types.
        using Int32NodeCache = NodeCache<int32_t>;
        using Int64NodeCache = NodeCache<int64_t>;

        // All we want is the numeric value of the RelocInfo::Mode enum. We typedef
        // below to avoid pulling in assembler.h
        using RelocInfoMode = char;
        using RelocInt32Key = std::pair<int32_t, RelocInfoMode>;
        using RelocInt64Key = std::pair<int64_t, RelocInfoMode>;
        using RelocInt32NodeCache = NodeCache<RelocInt32Key>;
        using RelocInt64NodeCache = NodeCache<RelocInt64Key>;
#if V8_HOST_ARCH_32_BIT
        using IntPtrNodeCache = Int32NodeCache;
#else
        using IntPtrNodeCache = Int64NodeCache;
#endif

        // Explicit instantiation declarations.
        extern template class EXPORT_TEMPLATE_DECLARE(
            V8_EXPORT_PRIVATE) NodeCache<int32_t>;
        extern template class EXPORT_TEMPLATE_DECLARE(
            V8_EXPORT_PRIVATE) NodeCache<int64_t>;

        extern template class EXPORT_TEMPLATE_DECLARE(
            V8_EXPORT_PRIVATE) NodeCache<RelocInt32Key>;
        extern template class EXPORT_TEMPLATE_DECLARE(
            V8_EXPORT_PRIVATE) NodeCache<RelocInt64Key>;

    } // namespace compiler
} // namespace internal
} // namespace v8

#endif // V8_COMPILER_NODE_CACHE_H_
